Information or data can be stored relatively inexpensively in various magnetic or optical mass-storage devices such as tapes, disks or drums. These devices are slow, non-volatile, and only provide for access to large blocks of data. Silicon-based random access memory (RAM) is significantly faster, provides for random byte-by-byte access to data, but is volatile and more expensive. The difference in speed is often several orders of magnitude.
It is common practice in the computer industry to mass-store data in magnetic or optical mass-storage devices, transfer the data to RAM for use or modification, and then transfer the data back to the mass-storage devices. The use of RAM in this way permits the high speed processing of the data in a computer system. However, due to the slow speed of the mass-storage devices, the processing operation performed by the computer system is significantly delayed when more data is needed from a mass-storage device. Several methods are conventionally used to minimize such delays.
One common approach is the use of a cache memory. A cache memory is usually RAM and is normally embodied as part of the mass-storage controller. When the CPU requests data from a mass-storage device, the requested data is fetched from the mass-storage device along with a prefetch of more data than requested. Both the requested and prefetched data are loaded into the cache memory, the requested data for current use and the prefetched data in anticipation of subsequent use. Each subsequent request for data is first checked against the cache memory before it is fetched from a mass-storage device. Since data stored in the cache memory can be supplied to the computer RAM much faster than from a mass-storage device, processing speed is substantially enhanced especially if the prefetched data is anticipated correctly.
The most common method of prefetching is sequential prefetching. Sequential prefetching assumes that data requests will be made in order of logical sector address. Therefore, each request is accompanied by a prefetch at the next higher logical sector address. However, since prefetching requires the removal of one block of data from the cache memory for each block of data prefetched, it is sometimes best not to prefetch at all, thereby retaining more of the previously stored data in the cache memory. Since such previously stored data may be requested again, it is desirable to retain it in the cache as long as possible.
If a program requests information sequentially, sequential prefetching advantageously results in the requested data being in the cache memory before it is requested in most cases. However, as mentioned above, if prefetching causes the removal of data that will be used again in a short time, prefetching is a disadvantage. Programs generally perform some combination of requesting information sequentially and requesting information in some other pattern. It is, therefore, advantageous to prefetch sequentially when a process requests data sequentially and not prefetch sequentially when the processes does not request data sequentially.
When there is basic information about the source of the request or the source of the data, an educated guess can be made as to a good prefetching strategy. One such variable prefetching algorithm is disclosed in U.S. Pat. No. 3,898,624--Tobias, "Data Processing System with Variable Prefetch and Replacement Algorithms". When all data comes from a common mass-storage device such as a disk drive and no prior information is known about requests, past history is the only clue available as to future requests. The present invention uses past history to determine whether or not to prefetch and the amount of data to prefetch.